具有固定行列和k的阶为2k-2的(0,1)-矩阵的最大跳跃数

1992年Brualdi与Jung首次引出了最大跳跃数M(n,k),即每行每列均含k个1的阶为n的(0,1)-矩阵的跳跃数的极大数,给出了满足条件1≤k ≤n ≤10的(0,1)-矩阵的最大跳跃数M(n,k)的一个表,并提出了几个猜想,其中包括猜想M(2k-2,k)=3k-4 [k-2/2].本文证明了当k≥11时,对每个A∈∧(2k-2,k)有b(A)≥4.还得到了该猜想的另一个反例.     

Minimal spanning trees with a constraint on the number of leaves

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a “degree-1” terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in “degree-1” terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of “degree-1” terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.